import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class CutOffTree {
    // 为高尔夫比赛砍树
    // https://leetcode.cn/problems/cut-off-trees-for-golf-event/
    private int m;
    private int n;
    public int cutOffTree(List<List<Integer>> forest) {
        // 因为砍树的顺序需要是从低到高的，所以我们首先需要知道森林中的树的高矮顺序
        m = forest.size();
        n = forest.get(0).size();
        List<int[]> trees = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (forest.get(i).get(j) > 1) {
                    trees.add(new int[]{i,j});
                }
            }
        }
        Collections.sort(trees, (a, b) -> {
            return forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]);
        });
        // 因为题目中求的是按从小到大的顺序砍树的最少步数
        // 那么就可以转换成从一个点到另一个点的最短距离
        // 从[0,0]开始
        int bx = 0, by = 0;
        int ret = 0;
        // 遍历升序排序的树
        for (int[] tree : trees) {
            int x = tree[0];
            int y = tree[1];
            int step = bfs(forest, bx, by, x, y);
            if (step == -1) {
                return -1;
            }
            ret += step;
            // 将开始位置更新为当前位置
            bx = x;
            by = y;
        }
        return ret;
    }

    int[] dx = {-1,0,0,1};
    int[] dy = {0,-1,1,0};
    private int bfs(List<List<Integer>> forest, int bx, int by, int ex, int ey) {
        if (bx == ex && by == ey) {
            return 0;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{bx, by});
        boolean[][] vis = new boolean[m][n];
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            step++;
            while (size-- > 0) {
                int[] tmp = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int x = tmp[0] + dx[i];
                    int y = tmp[1] + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && forest.get(x).get(y) != 0
                            && !vis[x][y]) {
                        if (x == ex && y == ey) {
                            return step;
                        }
                        queue.add(new int[]{x,y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
}
